The field of computer graphics concerns the creation, storage, manipulation and display of pictures and models of objects by a digital processor. Interactive computer graphics is the subclass of computer graphics in which a user dynamically controls the picture's content, format, size or color on a display surface by means of an interaction device such as a keyboard, lever or joystick. See Fundamentals of Interactive Computer Graphics, by J. D. Foley and A. Van Dam, ISBN: 0-201-14468-9. The creation of synthetic images (i.e., images which exist as abstract collections of lines, points, curves, etc., in the computer's memory) is the usual domain of interactive computer graphics.
There are two primary classes of interactive computer graphics systems: random-scan and raster-scan systems. Images displayed by a random-scan system are encoded as commands to draw each output primitive (i.e., point, line or polygon) by plotting individual points or drawing connecting lines between specified starting and ending coordinates of line segments. Polygons are simply treated as a closed series of line segments. Encoding for a raster-scan system is much simpler: output primitives are broken up into their constituent points for display. The major difference between a simple point-plotting random-scan system and a raster-scan system is in the organization of the stored data used to drive the display. As explained below, the data is stored in a "frame buffer" (also called a "refresh buffer").
In the random-scan system, the component points of each successive output primitive are stored sequentially in memory and are plotted in that order, one point at a time. This is because the beam may be moved randomly on the screen. In the raster-scan system, the refresh memory is arranged as a 2-dimensional array of data. The value stored at a particular row and column encodes an intensity and/or color value of a corresponding display element on the screen. By convention, the location of each display element is specified by a unique (X,Y) coordinate.
Since each memory location defines a single point-sized element of an image, both the display screen location and its corresponding memory location are often called a "pixel," short for the image processing term "picture element." Hereinafter, to avoid confusion, we'll use the term "display pixel" to indicate picture elements of a display device, and "storage pixel" to indicate memory locations corresponding to the display pixels.
FIG. 1 is a simplified block diagram of a raster-scan graphic system 10. Such a system includes an image creation system 12, an image storage system 14 (such as a frame buffer), an image display system 16, a raster-scan display 18 and an interaction device 20. The image creation system 12 converts output primitives into the data stored in the frame buffer of the image storage system 14. The processing speed of the image creation system 12 establishes most of the characteristics of the raster-scan system 10. Moreover, the image creation system 12 is particularly malleable because it is typically implemented with a microprocessor. See Chapter 12 of Fundamentals of Interactive Computer Graphics, referenced above.
The overall speed with which all or part of the stored image data can be changed is dependent upon, among other things, how fast the image creation system executes instructions. It is the image creation system's execution of instructions which is often the slowest process in creating or changing an image. This is because the "scan conversion" algorithm (described below) typically requires many iterations. Usually, the faster the scan conversion algorithm, the faster the overall system response time to user commands. In addition, it is known that response time is critical to user satisfaction and, perhaps more importantly, to user productivity.
The process of converting a line, point, and area representation of an image to the array of pixel data in the image storage system 14 is called "scan conversion." Scan conversion algorithms are always needed in an interactive raster-scan graphics system, and are usually incorporated into the image creation system 12. The scan conversion algorithm used in a raster-scan graphics system will be invoked quite often, typically hundreds or even thousands of times, each time an image is created or modified. Hence, it must not only create visually pleasing images, but must also execute as rapidly as possible. Indeed speed versus image quality is the basic tradeoff in known scan conversion algorithms. Some scan conversion algorithms are fast and give jagged edges, while others are slower but give smoother edges. However, it can generally be said that faster is better for a given smoothness of image.
FIG. 2 depicts an exemplary line, y=mx+b, along with a vector 22 as it might be rendered (i.e., stored) in the frame buffer of the image storage system 14. Vector 22 is composed of a set of display pixels P.sub.0, P.sub.1, P.sub.2, . . . P.sub.N driven by a corresponding set of storage pixels in the image storage system 14. Vector 22 is rendered by stepping along the major axis, in this case the X-axis, and computing corresponding minor axis (Y-axis) ordinate values. These (X,Y) coordinates define the storage and display pixels composing the vector 22. The basic task in scan converting a line is to compute the integer coordinates of the display pixels lying nearest the line.
As can be seen from vector 22, the limited resolution of the frame buffer 14 and display device 18 causes the vector to become jagged, or "aliased." Techniques for generating antialiased (i.e., smooth) vectors are known in the art. See, for example, Chapter 11.2.3 of Fundamentals of Interactive Computer Graphics, referenced above, and references cited therein for details of known antialiasing techniques. These known antialiasing techniques are too slow for many applications however, although they may produce visually acceptable images.
FIGS. 3(a) and 3(c) depict two sets of vectors. The end point description of the set shown in FIG. 3(a) is a simple horizontal translation of the end point description of the set shown in FIG. 3(c). Both sets of vectors have a slope of 1/200. The vectors of FIG. 3(a) have been filtered, i.e., are antialiased, while the vectors of FIG. 3(c) are aliased.
The spatial aliasing shown by the unfiltered set of vectors in FIG. 3(c) is not the only aliasing problem in computer generated graphics. Another aliasing problem is shown in FIGS. 3(b) and 3(d). The vectors shown in FIG. 3(b) are the same as those in FIG. 3(a), and the vectors shown in FIG. 3(d) are the same as those shown in FIG. 3(c), with the exception that the vectors shown in FIGS. 3(b) and 3(d) have been translated vertically by one-half of a pixel. If these two sets of aliased and antialiased vectors are displayed as part of a real time series, then the antialiased vectors would have the correct apparent motion; that is, the antialiased vectors would appear to be slowly moving up. On the other hand, the aliased vectors would appear to be moving quickly in the horizontal direction. The arrow in FIG. 3(d) points to a step in the displayed pixels. This step is noticeably offset from the equivalent step in FIG. 3(c). It is the motion of these steps that dominate the apparent motion of the unfiltered vectors in the real time series. In other words, the image on the right would appear to moving at the wrong speed in the wrong direction. This artifact is called "aliasing-induced motion." A viewer sees a combination of all aliasing artifacts, including those due to both spatial aliasing and aliasing-induced motion. As pixel rendering speed increases and the goal of real-time generation of images is approached, aliasing-induced motion becomes greater and the total aliasing problem becomes more troublesome. See A. C. Barkans, "High Speed High Quality Antialiased Vector Generation," Computer Graphics, Vol. 24, Number 4, August 1990, which is incorporated herein by reference.
Users of interactive graphics systems now expect vector generation to be fast enough to support the real time display of user-controlled complex images. This has unfortunately aggravated the aliasing problem since aliasing-induced motion is added to the formerly dominant static spatial aliasing.